package com.gxc.tree;

/**
 * 给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
 */
public class MostBinaryTreeStructures {

    public static void main(String[] args) {
        System.out.println(recursionProcess(3));
        System.out.println(dpProcess(3));

        System.out.println(recursionProcess(8));
        System.out.println(dpProcess(8));
    }

    /**
     * 剩余n个节点时，可构成的二叉树结构数量
     * 递归
     * @param n
     * @return
     */
    public static int recursionProcess(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;

        //左树从0到n-1个节点，意味着右树从n-1到0个节点
        int sum = 0;
        for (int i = 0; i <= n-1; i++) {
            int left = recursionProcess(i);
            int right = recursionProcess(n-1-i);
            sum += left*right;
        }
        return sum;
    }

    /**
     * 剩余n个节点时，可构成的二叉树结构数量
     * dp
     * @param n  剩余n个节点时，可构成的二叉树结构数量
     * @return
     */
    public static int dpProcess(int n) {
        if (n<2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n+1; i++) {
            for (int j = 0;j<i;j++) {
                dp[i] += dp[i-j-1]*dp[j];
            }
        }
        return dp[n];
    }

}
